home *** CD-ROM | disk | FTP | other *** search
/ Shareware Grab Bag / Shareware Grab Bag.iso / 010 / maze.arc / SMAZE.PAS < prev   
Encoding:
Pascal/Delphi Source File  |  1986-09-24  |  12.1 KB  |  359 lines
  1. PROGRAM solve;
  2.   {
  3.          This program solves a maze generated by the program EMAZE.PAS.
  4.     It prints the solution on an Epson MX-80 printer.
  5.   
  6.          Written by James L. Dean
  7.                     406 40th Street
  8.                     New Orleans, LA 70124
  9.   }
  10.   CONST
  11.     num_columns = 95; 
  12.     x_max = 190;      {2*num_columns}
  13.     num_rows = 120;
  14.     y_max = 240;      {2*num_rows}
  15.   TYPE
  16.     stack_rec_ptr = ^stack_rec;
  17.     stack_rec = RECORD
  18.                   index_1 : BYTE;
  19.                   index_2 : BYTE;
  20.                   next_ptr : stack_rec_ptr
  21.                 END;
  22.   VAR
  23.     column                     : INTEGER;
  24.     column_mod_2               : INTEGER;
  25.     column_mod_5               : INTEGER;
  26.     delta_index_1              : INTEGER;
  27.     delta_index_1a             : INTEGER;
  28.     delta_index_1b             : INTEGER;
  29.     delta_index_1c             : INTEGER;
  30.     delta_index_1d             : INTEGER;
  31.     delta_index_2              : INTEGER;
  32.     delta_x                    : ARRAY [1..4,1..24] OF INTEGER;
  33.     delta_y                    : ARRAY [1..4,1..24] OF INTEGER;
  34.     page                       : ARRAY [0..y_max,0..x_max] OF CHAR;
  35.     passage_found              : BOOLEAN;
  36.     power_of_two               : INTEGER;
  37.     print_line                 : ARRAY[0..479] OF BYTE;
  38.     r_n                        : ARRAY [1..8] OF INTEGER;
  39.     r_n_index_1                : INTEGER;
  40.     r_n_index_2                : INTEGER;
  41.     response                   : CHAR;
  42.     row_mod_2                  : INTEGER;
  43.     row_mod_6                  : INTEGER;
  44.     seed                       : STRING[8];
  45.     stack_head                 : stack_rec_ptr;
  46.     stack_ptr                  : stack_rec_ptr;
  47.     tem_int                    : INTEGER;
  48.     x                          : INTEGER;
  49.     x_next                     : INTEGER;
  50.     x_out                      : INTEGER;
  51.     x_previous                 : INTEGER;
  52.     x_wall_1                   : INTEGER;
  53.     y                          : INTEGER;
  54.     y_next                     : INTEGER;
  55.     y_previous                 : INTEGER;
  56.     y_out                      : INTEGER;
  57.     y_wall_1                   : INTEGER;
  58.   BEGIN
  59.     ClrScr;
  60.     WRITELN(OUTPUT,'                                  Maze Solver');
  61.     WRITELN(OUTPUT,' '); WRITELN(OUTPUT,' '); WRITELN(OUTPUT,' ');
  62.     WRITE(OUTPUT,'Seed?  ');
  63.     READLN(INPUT,seed);
  64.     WHILE (Length(seed) < 8) DO seed:=CONCAT('0',seed);
  65.     WRITELN(OUTPUT,' ');
  66.     WRITELN(OUTPUT,'Generating maze...');
  67.     delta_x[1,1]:=-1;
  68.     delta_y[1,1]:=0;
  69.     delta_x[2,1]:=0;
  70.     delta_y[2,1]:=1;
  71.     delta_x[3,1]:=1;
  72.     delta_y[3,1]:=0;
  73.     delta_x[4,1]:=0;
  74.     delta_y[4,1]:=-1;
  75.     delta_index_2:=0;
  76.     FOR delta_index_1a:=1 TO 4 DO
  77.       FOR delta_index_1b:=1 TO 4 DO
  78.         IF delta_index_1a <> delta_index_1b THEN
  79.           FOR delta_index_1c:=1 TO 4 DO
  80.             IF ((delta_index_1a <> delta_index_1c)
  81.             AND (delta_index_1b <> delta_index_1c)) THEN
  82.               FOR delta_index_1d:=1 TO 4 DO
  83.                 IF ((delta_index_1a <> delta_index_1d)
  84.                 AND (delta_index_1b <> delta_index_1d)
  85.                 AND (delta_index_1c <> delta_index_1d)) THEN
  86.                   BEGIN
  87.                     delta_index_2:=delta_index_2+1;
  88.                     delta_x[delta_index_1a,delta_index_2]:=delta_x[1,1];
  89.                     delta_y[delta_index_1a,delta_index_2]:=delta_y[1,1];
  90.                     delta_x[delta_index_1b,delta_index_2]:=delta_x[2,1];
  91.                     delta_y[delta_index_1b,delta_index_2]:=delta_y[2,1];
  92.                     delta_x[delta_index_1c,delta_index_2]:=delta_x[3,1];
  93.                     delta_y[delta_index_1c,delta_index_2]:=delta_y[3,1];
  94.                     delta_x[delta_index_1d,delta_index_2]:=delta_x[4,1];
  95.                     delta_y[delta_index_1d,delta_index_2]:=delta_y[4,1]
  96.                   END;
  97.     FOR r_n_index_1:=1 TO 8 DO
  98.       BEGIN
  99.         tem_int:=ORD(seed[r_n_index_1]);
  100.         WHILE (tem_int > 29) DO tem_int:=tem_int-29;
  101.         IF tem_int = 0 THEN tem_int:=1;
  102.         r_n[r_n_index_1]:=tem_int
  103.       END;
  104.     FOR x_out:=0 TO x_max DO
  105.       FOR y_out:=0 TO y_max DO
  106.         page[y_out,x_out]:='W';
  107.     IF ODD(num_columns) THEN
  108.       x:=num_columns
  109.     ELSE
  110.       x:=(num_columns-1);
  111.     IF ODD(num_rows) THEN
  112.       y:=num_rows
  113.     ELSE
  114.       y:=(num_rows-1);
  115.     page[y,x]:=' ';
  116.     stack_head:=NIL;
  117.     REPEAT
  118.       delta_index_1:=1;
  119.       REPEAT
  120.         delta_index_2:=r_n[1];
  121.         r_n_index_1:=1;
  122.         FOR r_n_index_2:=2 TO 8 DO
  123.           BEGIN
  124.             tem_int:=r_n[r_n_index_2];
  125.             r_n[r_n_index_1]:=tem_int;
  126.             delta_index_2:=delta_index_2+tem_int;
  127.             IF delta_index_2 > 29 THEN
  128.               delta_index_2:=delta_index_2-29;
  129.             r_n_index_1:=r_n_index_2
  130.           END;
  131.         r_n[8]:=delta_index_2
  132.       UNTIL
  133.         (delta_index_2 <= 24);
  134.       passage_found:=FALSE;
  135.       REPEAT
  136.         WHILE ((delta_index_1 <= 4) AND (NOT passage_found)) DO
  137.           BEGIN
  138.             x_next:=x+2*delta_x[delta_index_1,delta_index_2];
  139.              IF x_next <= 0 THEN
  140.               delta_index_1:=delta_index_1+1
  141.              ELSE
  142.               IF x_next >= x_max THEN
  143.                 delta_index_1:=delta_index_1+1
  144.               ELSE
  145.                 BEGIN
  146.                   y_next:=y+2*delta_y[delta_index_1,delta_index_2];
  147.                   IF y_next <= 0 THEN
  148.                     delta_index_1:=delta_index_1+1
  149.                   ELSE
  150.                     IF y_next >= y_max THEN
  151.                       delta_index_1:=delta_index_1+1
  152.                     ELSE
  153.                       IF page[y_next,x_next] = 'W' THEN
  154.                         passage_found:=TRUE
  155.                       ELSE
  156.                         delta_index_1:=delta_index_1+1
  157.                 END
  158.           END;
  159.         IF (NOT passage_found) THEN
  160.           BEGIN
  161.             delta_index_1:=stack_head^.index_1;
  162.             delta_index_2:=stack_head^.index_2;
  163.             x:=x-2*delta_x[delta_index_1,delta_index_2];
  164.             y:=y-2*delta_y[delta_index_1,delta_index_2];
  165.             stack_ptr:=stack_head;
  166.             stack_head:=stack_head^.next_ptr;
  167.             DISPOSE(stack_ptr);
  168.             delta_index_1:=delta_index_1+1
  169.           END
  170.       UNTIL ((passage_found) OR (stack_head = NIL));
  171.       IF passage_found THEN
  172.         BEGIN
  173.           NEW(stack_ptr);
  174.           stack_ptr^.next_ptr:=stack_head;
  175.           stack_head:=stack_ptr;
  176.           stack_head^.index_1:=delta_index_1;
  177.           stack_head^.index_2:=delta_index_2;
  178.           page[y_next,x_next]:=' ';
  179.           IF x = x_next THEN
  180.             BEGIN
  181.               y_wall_1:=(y+y_next) DIV 2;
  182.               page[y_wall_1,x_next]:=' '
  183.             END
  184.           ELSE
  185.             BEGIN
  186.               x_wall_1:=(x+x_next) DIV 2;
  187.               page[y_next,x_wall_1]:=' '
  188.             END;
  189.           x:=x_next;
  190.           y:=y_next
  191.         END
  192.     UNTIL (stack_head = NIL);
  193.     page[0,1]:=' ';
  194.     page[y_max,x_max-1]:=' ';
  195.     WRITELN(OUTPUT,' ');
  196.     WRITELN(OUTPUT,'Solving maze...');
  197.     x:=1;
  198.     y:=1;
  199.     x_previous:=x;
  200.     y_previous:=-y;
  201.     FOR y_out:=0 TO y DO
  202.       page[y_out,x]:='S';
  203.     REPEAT
  204.       delta_index_1:=1;
  205.       passage_found:=FALSE;
  206.       REPEAT
  207.         WHILE ((delta_index_1 <= 4) AND (NOT passage_found)) DO
  208.           BEGIN
  209.             x_next:=x+delta_x[delta_index_1,1];
  210.             y_next:=y+delta_y[delta_index_1,1];
  211.             IF page[y_next,x_next] = ' ' THEN
  212.               passage_found:=TRUE
  213.             ELSE
  214.               delta_index_1:=delta_index_1+1
  215.           END;
  216.         IF (NOT passage_found) THEN
  217.           BEGIN
  218.             delta_index_1:=stack_head^.index_1;
  219.             x_previous:=x-2*delta_x[delta_index_1,1];
  220.             y_previous:=y-2*delta_y[delta_index_1,1];
  221.             IF x = x_previous THEN
  222.               IF y <= y_previous THEN
  223.                 FOR y_out:=y TO y_previous DO
  224.                   page[y_out,x]:=' '
  225.               ELSE
  226.                 FOR y_out:=y_previous TO y DO
  227.                   page[y_out,x]:=' '
  228.             ELSE
  229.               IF x <= x_previous THEN
  230.                 FOR x_out:=x TO x_previous DO
  231.                   page[y,x_out]:=' '
  232.               ELSE
  233.                 FOR x_out:=x_previous TO x DO
  234.                   page[y,x_out]:=' ';
  235.             x:=x_previous;
  236.             y:=y_previous;
  237.             stack_ptr:=stack_head;
  238.             stack_head:=stack_head^.next_ptr;
  239.             DISPOSE(stack_ptr);
  240.             delta_index_1:=delta_index_1+1
  241.           END
  242.       UNTIL (passage_found);
  243.       x_next:=x_next+delta_x[delta_index_1,1];
  244.       y_next:=y_next+delta_y[delta_index_1,1];
  245.       IF y_next <= y_max THEN
  246.         BEGIN
  247.           NEW(stack_ptr);
  248.           stack_ptr^.next_ptr:=stack_head;
  249.           stack_head:=stack_ptr;
  250.           stack_head^.index_1:=delta_index_1;
  251.           IF x = x_next THEN
  252.             IF y <= y_next THEN
  253.               FOR y_out:=y TO y_next DO
  254.                 page[y_out,x]:='S'
  255.             ELSE
  256.               FOR y_out:=y_next TO y DO
  257.                 page[y_out,x]:='S'
  258.           ELSE
  259.             IF x <= x_next THEN
  260.               FOR x_out:=x TO x_next DO
  261.                 page[y,x_out]:='S'
  262.             ELSE
  263.               FOR x_out:=x_next TO x DO
  264.                 page[y,x_out]:='S';
  265.           x:=x_next;
  266.           y:=y_next
  267.         END
  268.     UNTIL (y_next > y_max);
  269.     FOR y_out:=y TO y_max DO
  270.       page[y_out,x]:='S';
  271.     WHILE (stack_head <> NIL) DO
  272.       BEGIN
  273.         stack_ptr:=stack_head;
  274.         stack_head:=stack_head^.next_ptr;
  275.         DISPOSE(stack_ptr)
  276.       END;
  277.     WRITELN(OUTPUT,' ');
  278.     WRITELN(OUTPUT,'Position your paper at top of form and press RETURN.');
  279.     READLN(INPUT,response);
  280.     WRITELN(OUTPUT,'Outputting solution...');
  281.     WRITE(LST,CHR(27)); WRITE(LST,'A'); WRITE(LST,CHR(8));
  282.     WRITE(LST,CHR(27),'2');
  283.     power_of_two:=128;
  284.     FOR column:=0 TO 479 DO
  285.       print_line[column]:=0;
  286.     row_mod_2:=0;
  287.     row_mod_6:=0;
  288.     y_out:=0;
  289.     WHILE (y_out <= y_max) DO
  290.       BEGIN
  291.         column:=0;
  292.         column_mod_2:=0;
  293.         column_mod_5:=0;
  294.         x_out:=0;
  295.         WHILE (x_out <= x_max) DO
  296.           BEGIN
  297.             IF page[y_out,x_out] = 'W' THEN
  298.               print_line[column]:=print_line[column]+power_of_two
  299.             ELSE
  300.               BEGIN
  301.                 IF row_mod_2 = 0 THEN
  302.                   BEGIN
  303.                     IF column_mod_2 = 0 THEN
  304.                       BEGIN
  305.                         IF page[y_out,x_out] = 'S' THEN
  306.                           BEGIN
  307.                             print_line[column]:=print_line[column]+power_of_two
  308.                           END
  309.                       END
  310.                   END
  311.               END;
  312.             IF column_mod_5 = 0 THEN
  313.               x_out:=x_out+1;
  314.             column:=column+1;
  315.             column_mod_2:=column_mod_2+1;
  316.             IF column_mod_2 >= 2 THEN
  317.               column_mod_2:=0;
  318.             column_mod_5:=column_mod_5+1;
  319.             IF column_mod_5 >= 5 THEN
  320.               BEGIN
  321.                 column_mod_5:=0;
  322.                 x_out:=x_out+1
  323.               END
  324.           END;
  325.         power_of_two:=power_of_two DIV 2;
  326.         IF power_of_two = 0 THEN
  327.           BEGIN
  328.             WRITE(LST,CHR(27)); WRITE(LST,'K');
  329.             WRITE(LST,CHR(224)); WRITE(LST,CHR(1));
  330.             power_of_two:=128;
  331.             FOR column:=0 TO 479 DO
  332.               BEGIN
  333.                 WRITE(LST,CHR(print_line[column]));
  334.                 print_line[column]:=0
  335.               END
  336.           END;
  337.         IF row_mod_6 = 0 THEN
  338.           y_out:=y_out+1;
  339.         row_mod_2:=row_mod_2+1;
  340.         IF row_mod_2 >= 2 THEN
  341.           row_mod_2:=0;
  342.         row_mod_6:=row_mod_6+1;
  343.         IF row_mod_6 >= 6 THEN
  344.           BEGIN
  345.             row_mod_6:=0;
  346.             y_out:=y_out+1
  347.           END
  348.       END;
  349.     WRITE(LST,CHR(27)); WRITE(LST,'K');
  350.     WRITE(LST,CHR(224)); WRITE(LST,CHR(1));
  351.     FOR column:=0 TO 479 DO
  352.       WRITE(LST,CHR(print_line[column]));
  353.     WRITE(LST,CHR(27)); WRITE(LST,'A',CHR(12),CHR(27),'2');
  354.     WRITELN(LST,' ');
  355.     WRITE(LST,'Seed:  '); WRITELN(LST,SEED);
  356.     WRITE(LST,CHR(12));
  357.     WRITE(LST,CHR(12))
  358.   END.
  359.